The present invention relates generally to summarization of an application profile and quick estimation of a network profile. The summarized application profile and the quickly estimated network profile facilitate partitioning and distribution of plural units of an application program by an automatic distributed partitioning system.
Fueled by the growing importance of the Internet, interest in the area of distributed systems (two or more computers connected by a network connection that supports communication between the computers, alternatively termed a xe2x80x9cdistributed computing environmentxe2x80x9d) has increased in recent years. Programmers desiring to take advantage of distributed systems modify existing application programs to perform on distributed systems, or design applications for placement on distributed systems.
A distributed application is an application containing interconnected application units (xe2x80x9cunitsxe2x80x9d) that are placed on more than one computer in a distributed system. By placing units on more than one computer in a distributed system, a distributed application can exploit the capabilities of the distributed system to share information and resources, and to increase application reliability and system extensibility. Further, a distributed application can efficiently utilize the varying resources of the computers in a distributed system.
Various types of modular software, including software designed in an object-oriented framework, can conceivably be distributed throughout a distributed system. Object-oriented programming models, such as the Microsoft Component Object Model (xe2x80x9cCOMxe2x80x9d), define a standard structure of software objects that can be interconnected and collectively assembled into an application (which, being assembled from component objects, is herein referred to as a xe2x80x9ccomponent applicationxe2x80x9d). The objects are hosted in an execution environment created by system services, such as the object execution environments provided by COM. This system exposes services for use by component application objects in the form of application programming interfaces (xe2x80x9cAPIsxe2x80x9d), system-provided objects and system-defined object interfaces. Distributed object systems such as Microsoft Corporation""s Distributed Component Object Model (DCOM) and the Object Management Group""s Common Object Request Broker Architecture (CORBA) provide system services that support execution of distributed applications.
In accordance with object-oriented programming principles, the component application is a collection of object classes which each model real world or abstract items by combining data to represent the item""s properties with functions to represent the item""s functionality. More specifically, an object is an instance of a programmer-defined type referred to as a class, which exhibits the characteristics of data encapsulation, polymorphism and inheritance. Data encapsulation refers to the combining of data (also referred to as properties of an object) with methods that operate on the data (also referred to as member functions of an object) into a unitary software component (i.e., the object), such that the object hides its internal composition, structure and operation and exposes its functionality to client programs that utilize the object only through one or more interfaces. An interface of the object is a group of semantically related member functions of the object. In other words, the client programs do not access the object""s data directly, but instead call functions on the object""s interfaces to operate on the data. Polymorphism refers to the ability to view (i.e., interact with) two similar objects through a common interface, thereby eliminating the need to differentiate between two objects. Inheritance refers to the derivation of different classes of objects from a base class, where the derived classes inherit the properties and characteristics of the base class.
An application containing easily identifiable and separable units is more easily distributed throughout a distributed system. One way to identify separable units is to describe such units with structural metadata about the units. Metadata is data that describes other data. In this context, structural metadata is data describing the structure of application units. Further, application units are desirably location-transparent for in-process, cross-process, and cross-computer communications. In other words, it is desirable for communications between application units to abstract away location of application units. This flexibly enables the distribution of application units.
The partitioning and distribution of applications are problematic and complicated by many factors.
To partition an application for distribution, a programmer typically determines a plan for distributing units of the application based on past experience, intuition, or data gathered from a prototype application. The application""s design is then tailored to the selected distribution plan. Even if the programmer selects a distribution plan that is optimal for a particular computer network, the present-day distribution plan might be rendered obsolete by changes in network topology. Moreover, assumptions used in choosing the distribution plan might later prove to be incorrect, resulting in an application poorly matched to its intended environment.
Generally, to distribute an application, one can work externally or internally relative to the application. External distribution mechanisms work without any modification of the application and include network file systems and remote windowing systems on a distributed system. Although external distribution mechanisms are easy to use and flexible, they often engender burdensome transfers of data between nodes of the distributed system, and for this reason are far from optimal. Internal distribution mechanisms typically modify the application to be distributed in various ways. Internal distribution mechanisms allow optimized application-specific distribution, but frequently entail an inordinate amount of extra programmer effort to find an improved distribution and modify the application. Further, internal systems frequently provide ad hoc, one-time results that are tied to the performance of a particular network at a particular time.
An automatic distributed partitioning system (ADPS) works internally relative to an application to partition application units, and works automatically or semi-automatically to save programmer effort in designing distributed applications.
In the 1970""s, researchers postulated that the best way to create a distributed application was to use a compiler in a run time environment to partition the application, and to provide the exact same code base to each of plural distributed machines as used on a single machine to execute the distributed application. After analyzing the structure of procedures and parameters in the source code of an application, metadata describing the structure of an application was generated from the application source code. Using this metadata, these ADPSs profiled the application and generate a communication model for the application. The Interconnected Processor System (ICOPS) is an example of an ADPS designed in the 1970""s. The Configurable Applications for Graphics Employing Satellites (CAGES) also supports creation of distributed applications, but does not support automatic application profiling at all. A more recent example of an ADPS is the Intelligent Dynamic Application Partitioning (IDAP) System. IDAP generates from application source code an instrumented version of the application for execution in profiling scenarios, then generates from application source code another version of the application for distributed execution. ICOPS and IDAP suffer from numerous drawbacks relating to the universality, efficiency, and automation of these systems.
An application profile is a model of an application. The application profile can include the units of an application and/or the costs of communication between units of the application according to expected usage patterns. An ADPS typically records inter-module communication in a trace file for later analysis. The size of such trace files can become prohibitively long during profiling. Nonetheless, neither ICOPS, CAGES, nor IDAP uses techniques to limit the size of such trace files.
Moreover, an ADPS typically represents communication costs between two communicating units of an application through one of several abstractions. For instance, in one abstraction, communication costs are represented as the time to transmit data between communicating units. This abstraction is network-dependent and changes with network interconnection. Another abstraction represents communication costs as an amount of data transmitted between communicating units. Yet another abstraction represents communication costs as a number of messages sent between communicating units. The latter two abstractions of communication costs fail to adequately consider the realities of network latencies and bandwidths, i.e., they fail to adequately consider network characteristics. Neither ICOPS, CAGES, nor IDAP abstracts communication costs in an application profile in a way that preserves meaningful network-independent description of inter-unit communication.
A network profile includes description of network characteristics such as network latency and bandwidth. Network latency relates to the time it takes one bit of information to travel across a computer network and back. Network bandwidth relates to the incremental time cost of transmitting one more bit of information across a computer network and back. Although latency is generally a linear function of bandwidth on a computer network, the function is not smooth.
On a particular computer network, a maximum transmission unit (MTU) is the largest size packet that can be sent across a network. Messages of larger size are split into multiple packets. MTUs introduce discontinuities into the latency-bandwith function because an increase of a single byte in the size of a message creates an additional network packet. Moreover, because the MTU is different for different networks, and because other network irregularities prevent the latency-bandwidth function from being linear, it is difficult to predict theoretically the latency and bandwidth of a particular network. Neither ICOPS, CAGES, nor IDAP includes network profiling to estimate latency and bandwidth.
Network characteristics frequently change. Nevertheless, typical network profilers do not provide a mechanism for quickly estimating network characteristics. Typical network profilers estimate average latency and average bandwidth to describe a computer network. Accurate estimation of average latency and bandwidth takes a long time. Measurement of average latency and bandwidth for a period using measurements of sub-periods or using sampling produces inaccurate results. Typical network profilers do not yield an accurate characterization of network behavior using only a short-term statistical sample.
The present invention pertains to profiling of application programs and computer networks. An automatic distributed partitioning system (ADPS) profiles an application program to produce a network-independent summary of communication between the units of the application program. The ADPS profiles a computer network using short term sampling to estimate the characteristics of the network. The summarized application profile and the quickly estimated network profile facilitate partitioning and distribution of plural units of an application program by an automatic distributed partitioning system. Alternatively, the application profile summarization and quick estimation of network profile aspects of the present invention are implemented outside of the context of an ADPS.
In an illustrated embodiment, an ADPS profiles a network to estimate network latency and bandwidth using short term sampling. These characteristics are application program independent. Based on a short term sample, the ADPS estimates minimum latency for the computer network, recognizing that minimum latency is less likely to fluctuate rapidly with a small number of samples than average latency, and recognizing that minimum latency is a reasonable proxy for average latency. In the short term sampling, a first computer sends n messages to a second computer, and the second computer responds for each message. The message and the response are empty network packets. From the message and response round trip time, the ADPS calculate a latency value for each of the n samples. To find minimum latency, the ADPS selects the smallest calculated latency value from the n samples.
Recognizing that maximum bandwidth is a reasonable proxy for average bandwidth, the ADPS accurately estimates maximum bandwidth using short term sampling. For n samples, a non-empty message is split into multiple packets and sent across the computer network by a first computer to a second computer. The second computer sends back a response, which can be empty or non-empty. The ADPS calculates a latency value for each sample. The ADPS then finds the minimum latency value for the non-empty messages. From the minimum latency values for empty and non-empty messages, and the size of the non-empty message, the ADPS calculates a maximum bandwidth estimate.
In an alternative embodiment, a combination of average network values and short term sampled network values facilitate partitioning and distribution of an application program by an ADPS.
In the illustrated embodiment, the ADPS profiles an application program to produce a summary of communication between units of the application program. The summary is a network-independent description. For a pair of communicating units, the summary logs message information. The summary can log a size value for each message sent between the pair of units. Alternatively, the summary can summarize messages sent between the pair of units as the messages are detected.
The summary records the number of messages sent between the pair of units and the size of messages sent. For the size of messages, the summary can record average size or total size. The summary can record this information for all messages, or for specific sub-ranges of message sizes. A message bucket is a sub-range of message sizes. A message bucket includes the number of messages in the message bucket and the total size of messages in the message bucket.
Message buckets form a series of contiguous size ranges for classifying messages. Messages buckets can be equally spaced, or spaced to correspond to a different expected behavior by messages in a computer network. For example, if a message of size k will be split into two packets, and a message of size k+1 will be split into 3 packets on a computer network, the two messages can be delegated to different message buckets. The configuration of message buckets can be determined by experimentation, by estimation of discontinuities in the latency-bandwidth function for a computer network, by theoretical analysis of MTU size for a computer network, or by other methods. From a library of message bucket configurations, an ADPS can select a particular configuration for a computer network.
In the illustrated embodiment, the ADPS determines a distribution plan for the application program in the computer network using the network and application profiles. Taken together, the network and application profiles accurately model the behavior of the application program on the computer network. The model is used to derive a distribution plan for application units, which are then distributed when the application program executes.
Additional features and advantages of the present invention will be made apparent from the following detailed description of an illustrated embodiment, which proceeds with reference to the accompanying drawings.